#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std ;

const int maxn =  1000010;  //稀疏图的顶点数更多

typedef pair<int , int > PII ;  //堆里面存的是顶点的编号和最短距离

int n , m ; //n 是点数  ， m 是边数
int h[maxn] , w[maxn] , e[maxn] , ne[maxn] , idx;  //用邻接表存
int dist[maxn] ;    //没个点的最短距离
bool st[maxn] ;     //这个点是不是已经确定了最短距离 --> S 集合

//加边
void add(int a , int b , int c) {
    e[idx] = b ;    //新加的结点的值指的是边的终点
    w[idx] = c ;    //权重用 w 来存
    ne[idx] = h[a] ;
    h[a] = idx ++;
}


int dijkstra() {
    memset(dist , 0x3f , sizeof dist) ;
    dist[1] = 0 ;   //初始化所有点的距离为 无穷 这里就说明了从下标 1 的地方开始存

    priority_queue<PII , vector<PII> , greater<PII> > heap ;    //小根堆
    heap.push({0 , 1}); //第一个点存进去，前一个是距离 ， 后一个是编号

    while(heap.size()) {
        //当前堆不为空
        auto t = heap.top();
        heap.pop()  ;   //弹出堆顶元素 ， 就是距离最小的元素

        int ver = t.second ;    //编号
        int distance = t.first ;    //距离

        if(st[ver]) {
            //如果这个点出现过，就直接跳过
            continue;
        }

        st[ver] = true;

        //遍历这个点的所有临边
        for(int i = h[ver] ; i != -1 ; i = ne[i] ) {    //只有跟ver邻接的点才会更新
            int j = e[i] ;  //存储这个点的编号，简写方式
            if(dist[j] > dist[ver] + w[i]) {   //权值不再是 g[i][j] ,   而是 w[i]
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j] , j}) ;  //将更新好了过后的点加入堆中 , 这里的插入相当于更新距离
            }
        }
    }

    if(dist[n] == 0x3f3f3f3f) {
        return -1 ;
    }
    return dist[n];
}


int  main() {

    scanf("%d%d" , &n , &m);

    memset(h , -1 , sizeof h) ;     //初始化所有点的距离为最大值

    while(m--) {
        //输入邻接矩阵    有自环和重边的 ， 自环不用管 ， 重边的话保留权值最小的那条边  ，
        int a , b , c ;
        scanf("%d%d%d" , &a , &b , &c) ;    //a , b 表示边的顶点 ，c表示边的权值
        add(a , b , c); //邻接表的话就不用判断重边了
    }

    int t = dijkstra();

    printf("%d\n" , t);

    return 0 ;
}
